package linkedList.迭代;

import linkedList.BaseLinkedListTest;
import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 排序链表148.java
 * @Description TODO https://leetcode-cn.com/problems/sort-list/
 * @createTime 2021年03月13日 11:34:00
 */
public class 排序链表148 extends BaseLinkedListTest {


    public static void main(String[] args) {
        ListNode listNode = sortList(createLinkedList(4, 2, 1, 3));
        System.out.println(listNode);
    }
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //进行分割
        return separateNodeList(head, null);
    }

    private static ListNode separateNodeList(ListNode head, ListNode tail) {
        //todo 分隔直到链表只包含一个或者两个接地
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            //因为分隔是[head,mid]和[mid,tail]进行分隔的，如果head=tail了说明只有两个节点了，这个时候第一个separateNodeList返回的是head，第二个separateNodeList返回的是tail
            head.next=null;
            return head;
        }
        //todo 用快慢指针找到链表的中点
        ListNode fastPoint = head.next, slowPoint = head;
        //如果快指针移动到了中点那么就需要停下
        while (fastPoint != tail) {
            slowPoint = slowPoint.next;
            fastPoint = fastPoint.next;
            if (fastPoint != tail) {
                fastPoint = fastPoint.next;
            }
        }
        //todo 继续分隔
        ListNode mid = slowPoint;
        ListNode left = separateNodeList(head, mid);
        ListNode right = separateNodeList(mid, tail);
        //todo 进行合并
        return mergeNodeList(left, right);
    }

    private static ListNode mergeNodeList(ListNode left, ListNode right) {

        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else if (left.val < right.val) {
            left.next = mergeNodeList(left.next, right);
            return left;
        } else {
            right.next = mergeNodeList(left, right.next);
            return right;
        }
    }
}
